package hot100;


/*
 * Author：江松
 * Date：2023/4/7 11:20
 *
 最长递增子序列：
 1，动态规划O(n^2)
 fi表示以num[i]结尾的最长递增子序列长度
 根据num[i]划分，从前i-1个数转移，大于就可以转移，反之就=1

 2,贪心策略+二分查找O(n*logN)
考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，
所以维护一个子序列数组，表示长度为i的最长上升子序列的“末尾”的最小值
如果后面的数大于数组中的最大值（最后），那么追加；反之，找到第一个>=这个数的位置(找到左边界)并替换
 */

public class Main300 {


    public int lengthOfLIS(int[] nums) {
        int n=nums.length;
        int a[]=new int[n];
        int len=1;
        a[0]=nums[0];
        for(int i=1;i<n;++i){
            if(nums[i]>a[len-1]){
                a[len++]=nums[i];
            }else{
                //二分查找>=k的第一个数
                int l=0,r=len-1;
                int k=nums[i];
                while(l<=r){
                    int mid=l+(r-l>>1);
                    if(a[mid]<k){
                        l=mid+1;
                    }else if(a[mid]>k){
                        r=mid-1;
                    }else{
                        //向左搜素
                        r=mid-1;
                    }
                }
                a[l]=k;
            }
        }
        return len;
    }

    /*
    public int lengthOfLIS(int[] nums) {
        int n=nums.length;
        int res=0;
        int f[]=new int[n+1];
        for(int i=1;i<=n;++i){
            f[i]=1;
            for(int j=1;j<i;++j){
                if(nums[i-1]>nums[j-1]){
                    f[i]=Math.max(f[i],f[j]+1);
                }
            }
            res=Math.max(res,f[i]);
        }
        return res;
    }
    */
}
